package 代码题.二维数组的题目;

/**
 * 在一个从左到右和从上到下都是递增的二维数组中寻找某个数是否存在
 */
public class FindNumIn2Arr {
    public static void main(String[] args) {
        int[][] arr=new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,16}
        };
        int k=10;
        System.out.println(findIn2Arr(arr,k));
    }

    /**
     * 默认最复杂的方法：使用二重循环遍历
     * 思路：从二维矩阵的右上角开始遍历，小的话向左走，大的话向下走
     *      越界走遍历结束。
     *      本质是做到有两个条件，每个走不同的道路
     * @param arr
     * @param k
     * @return
     */
    public static boolean findIn2Arr(int[][] arr,int k){
        int row=0;
        int col=arr[0].length-1;
        while (row<arr.length && col>=0){
            if(arr[row][col]==k){
                return true;
            }else if(k>arr[row][col]){
                row++;
            }else{
                col--;
            }
        }
        return false;
    }
}
